package medium;

/**
 * 53. 最大子数组和
 * 中等
 * 6.4K
 * 相关企业
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 */
public class T53 {
    public T53(int[] nums){
        // fn = fn-1+n
        System.out.println(dp(nums));
    }

    public int dp(int[] nums){
        int max  = nums[0];
        int lastF = 0;
        if (nums[0]>0){
            lastF = nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            if (lastF>0){
                lastF = lastF+nums[i];
            }else {
                lastF = nums[i];
            }
            if (lastF>max){
                max = lastF;
            }
        }
        return max;
    }

}
